import java.util.ArrayList;
import java.util.List;

/**
 * 二叉树-中序遍历-力扣94
 */

public class Practice_31 {
    public static void main(String[] args) {

        TreeNode head=new TreeNode(1);

        head.left=new TreeNode(2);

        head.right=new TreeNode(3);

        head.left.left=new TreeNode(4);

        head.left.right=new TreeNode(5);

        head.right.left=new TreeNode(6);

        head.right.right=new TreeNode(7);


        List<Integer> list= inorderTraversal(head);

    }

    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<>();

        helper(root,result);

        return result;
    }

    public static void helper(TreeNode head,List<Integer> result){
        if(head==null){
            return;
        }
        /* 前序遍历
        result.add(head.val);//前序遍历，取值在前面。
        helper(head.left,result);//先遍历左子树
        helper(head.right,result);//再遍历右子树*/


        //中序遍历
        helper(head.left,result);//先遍历左子树
        result.add(head.val);//中序遍历，取值在中间。
        helper(head.right,result);//再遍历右子树


         /* 后序遍历
          helper(head.left,result);//先遍历左子树
          helper(head.right,result);//再遍历右子树
          result.add(head.val);//后序遍历，取值在最后。*/


    }


    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val){
            this.val=val;
        }
    }
}
